package com.lsa.cormen.ch15.samples;

import java.io.IOException;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import com.lsa.helpers.IConverter;
import com.lsa.helpers.graph.AdjGraph;
import com.lsa.helpers.graph.IGraph;
import com.lsa.helpers.graph.TgfGraphFactory;

public class SubsetSum {
    static class NodeData{
        int node;
        int itemLevel; // corresponds to the item considered
        int weight;  // weight so far
        
        int parent; //will be determined by BFS
        boolean isTake; // toTake || !toTake - will be set by BFS
        
        Object attr;
        
        NodeData(int node, int itemLevel, int weight) {
            this.node = node;
            this.itemLevel = itemLevel;
            this.weight = weight;
        }

        NodeData(int itemLevel, int weight) {
            this.itemLevel = itemLevel;
            this.weight = weight;
        }
    }
    
    public static NodeData buildProblemGraph(IGraph<NodeData, Double> graph,
            int capacity, int[] weights) {
        int n = weights.length; // item count
        
        NodeData destination = null;
        
        NodeData nodeDate = new NodeData(0, 0, 0); // (0,0) node
        graph.addNode(nodeDate);
        
        Queue<NodeData> buildGraphQueue = new LinkedList<NodeData>();
        buildGraphQueue.add(nodeDate);
        
        /**
         * Class to store NodeData in the HT for the purpose of the reuse
         * @author lsa
         */
        class NodeDataKey{
            int itemLevel;
            int weight;
            
            NodeDataKey(int itemLevel, int weight) {
                this.itemLevel = itemLevel;
                this.weight = weight;
            }
            
            @Override
            public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + itemLevel;
                result = prime * result + weight;
                return result;
            }
            @Override
            public boolean equals(Object obj) {
                if (this == obj)
                    return true;
                if (obj == null)
                    return false;
                if (getClass() != obj.getClass())
                    return false;
                NodeDataKey other = (NodeDataKey) obj;
                if (itemLevel != other.itemLevel)
                    return false;
                if (weight != other.weight)
                    return false;
                return true;
            }
        }
        Map<NodeDataKey, NodeData> key2State = new HashMap<NodeDataKey, NodeData>();
        
        while(!buildGraphQueue.isEmpty()) {
            nodeDate = buildGraphQueue.poll();
            int u = nodeDate.node;
            
            if (nodeDate.itemLevel == n) {
                if (nodeDate.weight == capacity) {
                    destination = nodeDate;
                    break;
                }
                else{
                    continue;
                }
            }
            
           
            
            int nextItemLevel = nodeDate.itemLevel + 1;
            // 'not take' node
            int nextItemWeight = nodeDate.weight; 
            
            NodeDataKey key = new NodeDataKey(nextItemLevel, nextItemWeight);
            NodeData nextNodeData = key2State.get(key);
            int v1;
            if (nextNodeData == null) {
                nextNodeData = new NodeData(nextItemLevel, nextItemWeight);
                v1 = graph.addNode(nextNodeData);
                key2State.put(key, nextNodeData);
                nextNodeData.node = v1;
                buildGraphQueue.add(nextNodeData);
            }
            else {
                v1 = nextNodeData.node;
            }
            
            graph.addEdge(u, v1, 0.0);
            
            // 'take' node
            nextItemWeight = nodeDate.weight + weights[nodeDate.itemLevel];
            if (nextItemWeight <= capacity) {
                key = new NodeDataKey(nextItemLevel, nextItemWeight);
                nextNodeData = key2State.get(key);
                int v2;
                if (nextNodeData == null) {
                    nextNodeData = new NodeData(nextItemLevel, nextItemWeight);
                    v2 = graph.addNode(nextNodeData);
                    nextNodeData.node = v2;
                    buildGraphQueue.add(nextNodeData);
                }
                else {
                    v2 = nextNodeData.node;
                }
                
                graph.addEdge(u, v2, 1.0);
            }
        }
        
        return destination;
    }
    
    public static Integer[] subsetSumByBfs(int capacity, int[] weights) {
        IGraph<NodeData, Double> graph = new AdjGraph<NodeData, Double>(true, 0);
        
        NodeData node = buildProblemGraph(graph, capacity, weights);
        
        LinkedList<Integer> taken = new LinkedList<Integer>();
        
        if (node != null) {
            bfsShortestPath(graph, node);
            
            do{
                if (node.isTake) {
                    taken.addFirst(node.itemLevel-1);
                }
                node = graph.nodeAttr(node.parent);
            }
            while(node.itemLevel > 0);
        }
        
        try {
            TgfGraphFactory.saveGraphAsTgf(graph, new IConverter<NodeData, String>() {
                @Override
                public String convert(NodeData data) {
                    return String.format("l=%s,w=%s,t=%s", data.itemLevel, data.weight, data.isTake);
                }
            }, new IConverter<Double, String>() {

                @Override
                public String convert(Double data) {
                    return ""+data;
                }
            }, "data/gen/cormen/ch15/subsetSum.tgf");
        } catch (IOException e) {
            System.out.println(e);
        }
        
        return taken.toArray(new Integer[0]);
    }
    
    private static void bfsShortestPath(IGraph<NodeData, Double> graph,
            NodeData targetNode) {
        Deque<NodeData> queue = new LinkedList<NodeData>();
        queue.add(graph.nodeAttr(0));
out:
        while(!queue.isEmpty()) {
            NodeData uData = queue.poll();
            int u = uData.node;
            List<Integer> adj = graph.adjacencyList(uData.node);
            for (Integer v : adj) {
                NodeData vData = graph.nodeAttr(v);
                if (vData.attr == null) {
                    vData.attr = Boolean.TRUE;
                    vData.parent = u;
                    vData.isTake = graph.edgeAttr(u, v) > 0;
                    if (targetNode == vData) {
                        break out;
                    }else{
                        queue.add(vData);
                    }
                }
            }
        }
    }

    /**
     * @param S - capacity
     * @param weights
     * @return
     */
    public static Integer[] subsetSumByDp(int S, int[] weights) {
        class DP{
            int isExists;
            int parent = -1;
            boolean isTake;
        }
        
        int n = weights.length;
        
//        dp[i][j] is TRUE (1) if there is a subset of the gold bars 
//        i . . . n-1 (last n-i bars) which weighs
//        exactly j pounds
        DP[][] dp = new DP[n+1][S+1];
        dp[n][0] = new DP();
        dp[n][0].isExists = 1;
        
        for (int j = 1; j < S+1; j++) {
            dp[n][j] = new DP();
            dp[n][j].isExists = 0; 
        }
        
        for (int i = n-1; i > -1; i--) {
            for (int j = 0; j < S+1; j++) {
                // not use i-th item
                dp[i][j] = new DP();
                dp[i][j].isExists = dp[i+1][j].isExists;
                dp[i][j].parent = j;
                if (j - weights[i] > -1){
                    int takeDecision = dp[i+1][j - weights[i]].isExists;
                    if (takeDecision > dp[i][j].isExists) {
                        dp[i][j].isExists = takeDecision;
                        dp[i][j].parent = j - weights[i];
                        dp[i][j].isTake = true;
                    }
                }
            }
        }
        
        Deque<Integer> taken = new LinkedList<Integer>();
        if (dp[0][S].isExists == 1) {
            int parent = S;
            int i = 0;
            while(parent > -1) {
                if (dp[i][parent].isTake) {
                    taken.add(i);
                }
                parent = dp[i][parent].parent;
                i++;
            }
        }
        
        return taken.toArray(new Integer[0]);
    }
}
